package com.fe.class07.shoppingTopk;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @Description 使用加强堆结构解决
 * 候选区：O(N*logN)
 * 得奖区：O(N*logK)
 * 获取topk：O(K)
 * O(N*(logN+logK+K)) --> O(N*logN)
 * @Author sosuke :-)
 * @Date 2022/1/9 11:19
 */
public class ShoppingTopK {

    /**
     * 计算每次事件后的得奖topK
     *
     * @param arr 用户数组，元素表示用户ID，下标位置表示事件发生时间
     * @param op  事件数组，true表示购买，false表示退货
     * @param k   前k名得奖
     * @return
     */
    public static List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
        Map<Integer, Customer> map = new HashMap<>(); // 有资格参与比较的用户表
        // 候选区用户列表，加强堆
        HeapGreater<Customer> candidateArea = new HeapGreater<>(new CandidateAreaComparator());
        // 得奖区用户列表，加强堆
        HeapGreater<Customer> rewardArea = new HeapGreater<>(new RewardAreaComparator());
        List<List<Integer>> topkList = new ArrayList<>(); // 每次事件后的前k名用户ID列表
        for (int i = 0; i < arr.length; i++) {
            int id = arr[i];// 用户ID
            boolean event = op[i];// 发生事件
            if (!event && !map.containsKey(id)) { // 购买数为0，且当前事件为退货的，直接忽略，topk不变
                topkList.add(rewardArea.getAllElements().stream().map(c -> c.id).collect(Collectors.toList()));
                continue;
            }
            if (!map.containsKey(id)) { // 新用户
                Customer customer = new Customer(id, 0, i);
                map.put(id, customer);
                if (rewardArea.size() < k) {
                    rewardArea.push(customer);
                } else {
                    candidateArea.push(customer);
                }
            }
            Customer customer = map.get(id);
            // 购买、退货事件处理，并调整得奖区和候选区
            if (event) {
                customer.buy++;
            } else {
                customer.buy--;
            }
            if (customer.buy == 0) {
                map.remove(id);
                candidateArea.remove(customer);
                rewardArea.remove(customer);
            }
            // 涉及排序的字段buy发生变化了，需要调整堆
            candidateArea.resign(customer);
            rewardArea.resign(customer);
            // 事件后判断是否有用户需要从候选区或得奖区中移动
            move(candidateArea, rewardArea, k, i);
            // 记录这次事件后的topk列表
            topkList.add(rewardArea.getAllElements().stream().map(c -> c.id).collect(Collectors.toList()));
        }
        return topkList;
    }

    /**
     * 事件后判断是否有用户需要从候选区或得奖区中移动
     * @param candidateArea
     * @param rewardArea
     * @param k
     * @param time
     */
    private static void move(HeapGreater<Customer> candidateArea, HeapGreater<Customer> rewardArea, int k, int time) {
        if (candidateArea.isEmpty()) {
            return;
        }
        // 候选区不为空，且得奖区有用户购买数为0被清除了，所以不够k个了
        if (rewardArea.size() < k) {
            Customer customer = candidateArea.pop();
            customer.enterTime = time;
            rewardArea.push(customer);
        } else { // 得奖区满了，候选区有用户，判断是否可以替换得奖区的排序的首位
            if (candidateArea.peek().buy > rewardArea.peek().buy) {
                Customer candidateCustomer = candidateArea.pop();
                Customer rewardCustomer = rewardArea.pop();
                candidateCustomer.enterTime = time;
                rewardCustomer.enterTime = time;
                rewardArea.push(candidateCustomer);
                candidateArea.push(rewardCustomer);
            }
        }
    }

}
